<?php
/**
 * Created by PhpStorm.
 * User: lili
 * Date: 19-3-23
 * Time: 下午2:22
 */

require_once "../tools/tools.php";

if('cli'!==PHP_SAPI){
    echo "必须使用cli";
    exit();
}





echo "假设把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。 
习惯上我们把1当做是第一个丑数。求按从小到大的顺序排列的前n个丑数（以数组的形式返回）\n";



fwrite(STDOUT,"输入n:");
$n = trim(fgets(STDIN));


/**
 *
 * 暴力破解，自然数一个个从小到大，把所有的2、3、5除尽，最后等于1就是丑数
 *
 * @param $n
 * @return array
 *
 *
 */
function GetUglyNumber_Solution($n)
{
    $i=0;//计数，记录多少个丑数
    $z=0;//自然数
    $arr=[];
    while ($i<$n){
        $z++;
        $zt = $z;
        while (is_numeric($zt)&&strpos($zt,'.')===false){ //不是整数退出循环
            $zt = $zt/2;
        }
        $zt = $zt*2;

        while (is_numeric($zt)&&strpos($zt,'.')===false){ //不是整数退出循环
            $zt = $zt/3;
        }
        $zt = $zt*3;

        while (is_numeric($zt)&&strpos($zt,'.')===false){ //不是整数退出循环
            $zt = $zt/5;
        }
        $zt = $zt*5;

        if($zt==1){
            $i++;
            $arr[]=$z;
        }

    }
    return $arr;
}


$time_start = microtime_float();


echo  "丑数从小到大排列". ( implode(',',GetUglyNumber_Solution($n))       )."\n" ;

$time_end = microtime_float();
$time = $time_end - $time_start;

echo "Did nothing in $time seconds\n";